package com.sunjq;



public class HeapSort {

	

	public static void adjustHeap(int[] list, int node, int size) {
		int lChild = 2 * (node+1) -1;
		int rChild = 2 * (node + 1) ;
		int max = node;
		if (node <= size / 2 -1 ) {
			if (lChild <= (size-1) && list[lChild] > list[max]) {
				max = lChild;
			}
			if (rChild <= (size-1) && list[rChild] > list[max]) {
				max = rChild;
			}
			if (max != node) {
				int temp = list[node];
				list[node] = list[max];
				list[max] = temp;
				adjustHeap(list, max, size);
			}
			
		}

		System.out.println("ebug => start");
		for (int i = 0; i< list.length; i++) {
			
			System.out.print( list[i] + ", ");
		}
		System.out.println("ebug => edn");
	}

	public static void buildHeap(int[] list, int size) {
		for (int i = size/2 -1; i>=0; i--) {
			adjustHeap(list, i, size);
		}
	}
	
	public static void heapSort(int[] list) {
		buildHeap(list, list.length);
		for (int i = list.length-1; i>=0; i--) {
			int temp = list[i];
			list[i] = list[0];
			list[0] = temp;
			adjustHeap(list, 0,  i-1);
			
		}
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] list = {0,16,20,3,11,17,8};
		
		for (int i = 0; i< list.length; i++) {
			System.out.print(list[i] + ", ");
		}
		System.out.println();
		HeapSort.heapSort(list);

		for (int i = 0; i< list.length; i++) {
			System.out.print(list[i] + ", ");
		}
	}

}
